home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / c / globber.exe / README.DOC < prev   
Text File  |  1991-03-12  |  6KB  |  131 lines
  1. 03-12-91
  2.  
  3. This is V1.1 of REGEX Globber.
  4.  
  5.  
  6. 03-12-91
  7.  
  8. I have made a few changes to the match module which do several
  9. things.  The first change is an increase in bad pattern detection
  10. during a match.  It was possible, in some very unlikely cases, to
  11. cook up a pattern which should result in an early bad match but which
  12. would actually cause problems for the parser.  In particular, the
  13. subcase where the literal escape '\' within an open [..] construct at
  14. the end of a pattern would end up with incorrect results.  I
  15. proceeded to create some of these patterns, added them to my test
  16. battery and dove straight in.
  17.  
  18. In the interim I came across a posting to CompuServe (SMATCH by Stan
  19. Aderman) which attempted to create a completely non-recursive
  20. implementation of match (I am not sure this is possible without
  21. explicitly creating your own stack or it's equivelant, like a binary
  22. tree :-{ ).  While the code could not correctly handle multiple '*'
  23. characters in the pattern, there was a few interesting ideas in the
  24. posting.  On some occasions, running match over and over would be
  25. counter productive, especially and in particular when you have a bad
  26. pattern.  I have added a fast routine, is_valid_pattern(), to
  27. determine if the current pattern is well formed which should address
  28. this situation.
  29.  
  30. One other idea which I unceremoniously lifted from SMATCH was (in
  31. hindsight a pretty obvious feature) the return of a meaningful error
  32. code from both the pattern validity routine and from match() (which I
  33. renamed to matche()).
  34.  
  35. I also took some time to experiment with some ways to cut some time
  36. off the routine.  Since this is a SH pattern matcher whose intent is
  37. primarily for shell functions, the changes could not be algorithmic
  38. changes which relied on speedup over large input.  The differences in
  39. execution time were not very significant, but I did manage to gain
  40. approximately 5%-10% speedup when I removed the literal escape ('\')
  41. parsing and pattern error checking.  For those of you who want to use
  42. this for filename wildcard usage, I would recommend doing this since
  43. you should use is_valid_pattern and is_pattern before going out and
  44. finding filenames and the dos path delimiter defaults to the
  45. character used for the literal escape ('\') anyway (Note: I will be
  46. soon be releasing a *IX style file parser in the FINDFILE, FINDNEXT
  47. flavor soon to a Public Domain archive near you :-) ).
  48.  
  49. I also briefly toyed with adding a non-SH regex character '+' to this
  50. module but removed it again.  It was a performance hit of a few
  51. percent and would be mostly unused in any event.  For those
  52. interested in such a feature, the changes are truly minimal.  The
  53. required extra work is: 
  54.  
  55.    1) One case statement each in is_pattern() and is_valid_pattern() 
  56.    2) One case statement in matche()
  57.    3) One addition to a while conditional in matche_after_star()
  58.    4) One addition to an if conditional in matche_after_star()
  59.  
  60. Hint:  The case statements are all "case '+'" and the conditionals
  61.        have "|| *p == '+' " added to them.
  62.  
  63. I have also included a file (MATCH.DOC) which describes matches use and
  64. background as well as a little about regular expressions.
  65.  
  66.                                 jbk
  67.  
  68. 02-24-91
  69.  
  70. This is V1.01 of REGEX Globber.
  71.  
  72.  
  73. 02-22-91 Seattle, WA
  74.  
  75. Hmm. Choke. (Foot in mouth). After griping about buggy routines and
  76. literally seconds after posting this code the first time,  I received
  77. a wonderful new test evaluation tool which allows you to perform
  78. coverage analysis during testing.  Sure enough I found that about
  79. 25% of the paths in the program were never traversed in my current
  80. test battery.  After swallowing my (overly large) pride and coming
  81. up with a test battery which covered the entire path of the program
  82. I found a couple of minor logic bugs involving literal escapes (\)
  83. within other patterns (ie [..] and * sequences).  I have repackaged
  84. these routines and included also the makefile I use and the test
  85. battery I use to make things a bit easier.
  86.  
  87.                                 jbk
  88.  
  89. 02-20-91 Seattle, WA
  90.  
  91. Here is a *IX wildcard globber I butchered, hacked and cajoled together
  92. after seeing and hearing about and becoming disgusted with several similar
  93. routines which had one or more of the following attributes:  slow, buggy,
  94. required large levels of recursion on matches, required grotesque levels
  95. of recursion on failing matches using '*', full of caveats about usability
  96. or copyrights.
  97.  
  98. I submit this without copyright and with the clear understanding that
  99. this code may be used by anyone, for any reason, with any modifications
  100. and without any guarantees, warrantee or statements of usability of any
  101. sort.
  102.  
  103. Having gotten those cow chips out of the way, these routines are fairly
  104. well tested and reasonably fast.  I have made an effort to fail on all
  105. bad patterns and to quickly determine failing '*' patterns.  This parser
  106. will also do quite a bit of the '*' matching via quick linear loops versus
  107. the standard blind recursive descent.
  108.  
  109. This parser has been submitted to profilers at various stages of development
  110. and has come through quite well.  If the last millisecond is important to
  111. you then some time can be shaved by using stack allocated variables in
  112. place of many of the pointer follows (which may be done fairly often) found
  113. in regex_match and regex_match_after_star (ie *p, *t).
  114.  
  115. No attempt is made to provide general [pat,pat] comparisons.  The specific
  116. subcases supplied by these routines is [pat,text] which is sufficient
  117. for the large majority of cases (should you care).
  118.  
  119. Since regex_match may return one of three different values depending upon
  120. the pattern and text I have made a simple shell for convenience (match()).
  121. Also included is an is_pattern routine to quickly check a potential pattern
  122. for regex special characters.  I even placed this all in a header file for
  123. you lazy folks!
  124.  
  125. Having said all that, here is my own reinvention of the wheel.  Please
  126. enjoy it's use and I hope it is of some help to those with need ....
  127.  
  128.  
  129.                                 jbk
  130.  
  131.